package com.hejing.tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 二叉树功能测试:
        int size = 11;
        HeroNode[] arr = new HeroNode[] {
                new HeroNode(1, "宋江"),
                new HeroNode(2, "吴用"),
                null,
                null,
                new HeroNode(3, "卢俊义"),
                new HeroNode(4, "林冲"),
                null,
                null,
                new HeroNode(5, "李逵"),
                null,
                null
        };

        // 二叉树创建:
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = binaryTree.createBinaryTreeByPreOrder(arr);

        // 二叉树前序遍历
        System.out.println("前序遍历结果: ");
        binaryTree.preOrder(root);

        System.out.println("中序遍历结果: ");
        binaryTree.inOrder(root);

        System.out.println("后序遍历结果: ");
        binaryTree.postOrder(root);

        // 二叉树查找-前序遍历查找

    }

}


// 创建二叉树类
class BinaryTree {
    private int index = 0;  // 二叉树创建时的下标

    // 二叉树创建-前序数组创建
    public HeroNode createBinaryTreeByPreOrder(HeroNode[] arr) {
        HeroNode node =  arr[index++];
        if (node != null) {
            // 递归创建左子树
            node.left = createBinaryTreeByPreOrder(arr);
            // 递归创建右子树
            node.right = createBinaryTreeByPreOrder(arr);
        } else {
            return null;
        }
        return node;
    }


    // 二叉树前序遍历结果:
    public void preOrder(HeroNode root) {
        // 递归返回条件
        if (root == null) {
            return;
        }
        // 打印根节点
        System.out.println(root);
        // 递归遍历左子树
        if (root.left != null) {
            preOrder(root.left);
        }
        // 递归遍历右子树
        if (root.right != null) {
            preOrder(root.right);
        }
    }

    // 二叉树中序遍历结果:
    public void inOrder(HeroNode root) {
        // 递归返回条件
        if (root == null) {
            return;
        }
        // 递归遍历左子树
        if (root.left != null) {
            inOrder(root.left);
        }
        // 打印根节点信息
        System.out.println(root);
        // 递归遍历右子树
        if (root.right != null) {
            inOrder(root.right);
        }
    }

    // 二叉树后序遍历结果
    public void postOrder(HeroNode root) {
        // 递归结束条件
        if (root == null) {
            return;
        }
        // 递归遍历左子树
        if (root.left != null) {
            postOrder(root.left);
        }
        // 递归遍历右子树
        if (root.right != null) {
            postOrder(root.right);
        }
        // 打印根节点信息
        System.out.println(root);
    }

    // 二叉树前序查找

    /**
     *
     * @param node 查找二叉树的根节点
     * @param no 待查找节点的编号
     * @return
     */
    public HeroNode preOrderSearch(HeroNode node, int no) {
        if (node == null) {
            return null;
        }
        // 比较当前节点:
        if (node.no == no) {
            return node;
        }
        HeroNode node_temp = null;
        // 递归查找左子树
        if (node.left != null) {
            node_temp = preOrderSearch(node.left, no);
        }
        // 递归查找右子树
        if (node.right != null) {
            node_temp = preOrderSearch(node.right, no);
        }
        return node_temp;
    }

}

// 创建节点类:
class HeroNode {

    public int no;  // 英雄编号
    public String name;  // 英雄姓名
    public HeroNode left;  // 左节点
    public HeroNode right;  // 右节点

    public HeroNode() {

    }

    public HeroNode(int no, String name) {
        super();
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode(no: " + no +", name: " + name +")";
    }


    // 添加节点功能
    public void add(HeroNode node) {

    }
}


































